/*
题目描述：二叉搜索树的后序遍历序列
方法：最后一个结点为根节点，前面的结点序列可以分成两段，一段小于根节点的是左子树，大于根节点的是右子树
验证的方法就是先找到一个大于根节点的结点，从该节点向右找，如果还能找到比根节点小的结点，那么说明就不是二叉搜索树
 */
public class E33 {
    public static void main(String[] args) {
        int[] sequence = {5,7,6,9,11,10,8};
        boolean res = VerifySquenceOfBST(sequence);
        System.out.println(res);
    }

    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return helper(sequence, 0, sequence.length - 1);
    }

    public static boolean helper(int[] sequence, int left, int right){
        if(left >= right){
            return true;
        }
        int root = sequence[right];
        int split = left;
        for(; split < right && sequence[split] < root; split++);
        for(int i = split; i < right; i++){
            if(sequence[i] < root){
                return false;
            }
        }
        return helper(sequence, left, split - 1) && helper(sequence, split, right - 1);

    }
}
